import functools


class Solution(object):
    def maxCompatibilitySum(self, students, mentors):
        n = len(students)
        m = len(students)

        @functools.cache
        def dfs(i, val):
            if i == n:
                return 0
            else:
                max_val = 0
                for j in range(n):
                    if (val >> j) & 1 == 0:
                        now_val = sum([students[i][k] == mentors[j][k] for k in range(m)])
                        next_val = val | (1 << j)
                        max_val = max(max_val, now_val + dfs(i + 1, next_val))
                return max_val
        return dfs(0, 0)

